package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * 1458. 两个子序列的最大点积
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/28 15:08
 */
public class MaxDotProduct {

    public static void main(String[] args) {
        MaxDotProduct test = new MaxDotProduct();

        // 18
//        int[] arr1 = {2, 1, -2, 5};
//        int[] arr2 = {3, 0, -6};

        // 21
//        int[] arr1 = {3, -2};
//        int[] arr2 = {2, -6, 7};

        // -1
//        int[] arr1 = {-1, -1};
//        int[] arr2 = {1, 1};


        // 200
        int[] arr1 = {-3, -8, 3, -10, 1, 3, 9};
        int[] arr2 = {9, 2, 3, 7, -9, 1, -8, 5, -1, -1};

        // 200
//        int[] arr1 = {-3, -8, 3,};
//        int[] arr2 = {9, 2, 3, 7, -9, 1};

        int i = test.maxDotProduct(arr1, arr2);
        System.out.println(i);
    }

    public int maxDotProduct(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[][] arr = new int[m][n];
        arr[0][0] = nums1[0] * nums2[0];
        for (int i = 1; i < m; i++) {
            arr[i][0] = Math.max(arr[i - 1][0], nums1[i] * nums2[0]);
        }
        for (int i = 1; i < n; i++) {
            arr[0][i] = Math.max(arr[0][i - 1], nums1[0] * nums2[i]);
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                arr[i][j] = Math.max(Math.max(arr[i - 1][j], arr[i][j - 1]), Math.max(arr[i - 1][j - 1], Math.max(arr[i - 1][j - 1] + nums1[i] * nums2[j],nums1[i] * nums2[j] )));
            }
        }
        return arr[m - 1][n - 1];
    }

}
